#include <functional>
#include <algorithm>
#include <list>
#include "cmf.h"
#include "busqueda_local.h"
#include "iostream"


ostream& operator<<(ostream &os, list<vector<int> > lista);

ostream& operator<<(ostream &os, vector<int> &solucion);

bool operator==(vector<int> V1, vector<int> V2);

bool tercer_orden(vector<int> v1, vector<int> v2);

CliqueMaximaFronteraLocal::CliqueMaximaFronteraLocal(const Grafo& g) : CliqueMaximaFrontera(g) {
	
}


set<uint> CliqueMaximaFronteraLocal::resolver(vector<int> &clique) {		

list<vector<int> > cliques_binodos;


//Arma todas las cliques binódicas

int tam = grafo.cantidadNodos();

for(int i = 0; i < tam; i++){
	for(int j = i; j < tam; j++){
		vector<int> aux;
		if(grafo.adyacencia[i][j]){
			aux.push_back(i + 1);
			aux.push_back(j + 1);
			aux.push_back(grafo.miGrado(i + 1) + grafo.miGrado(j + 1) - 2); // = frontera
			cliques_binodos.push_back(aux);
		}
	}
}

cliques_binodos.sort(tercer_orden);


//Aca empieza a recorrer las vecindades

vector<int> aux_binodo;

bool tienen_iguales;

bool termine = false;

int repetido;

vector<int> CMFLocal;

if(clique.empty())
{
	CMFLocal = cliques_binodos.front();
	cliques_binodos.pop_front();
}
else
{
	CMFLocal = clique;
}

list<vector<int> > cliques_binodos_aux = cliques_binodos;

bool encontre_clique;

while(!termine){

encontre_clique = false;

	while(!(encontre_clique) && !(termine)){

	aux_binodo = cliques_binodos_aux.front();
	cliques_binodos_aux.pop_front();
	tienen_iguales = false;

		if(esCliqueMayorFrontera(CMFLocal, aux_binodo, tienen_iguales, repetido)){

			CMFLocal = unir(CMFLocal, aux_binodo, tienen_iguales, repetido);
			encontre_clique = true;
			cliques_binodos.remove(aux_binodo);
		}


	if(cliques_binodos_aux.empty()){ termine = true; }

	}

}

set<uint> resultado;

int CMFtam = CMFLocal.size();

	for(int k = 0; k < CMFtam; k++){

		resultado.insert(CMFLocal[k]);

	}

return resultado;

}





bool CliqueMaximaFronteraLocal::esCliqueMayorFrontera(vector<int> C1, vector<int> C2, bool& tiene_iguales, int& rep){

bool resultado = true;

int es_subgrafo = 0;

int tam = C1.size();


/******************************* Es clique? **************************************/
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < tam - 1; j++){
			if(C2[i] != C1[j]){
				if(!(grafo.adyacencia[C2[i] - 1][C1[j] - 1])){ resultado = false; }
			} else {
					tiene_iguales = true;
					rep = i;
					es_subgrafo++;
					if(es_subgrafo == 2) { resultado = false; }
				}

		}

	}
/**********************************************************************************/


/************************** Aumenta la frontera? **********************************/
	if(tiene_iguales){

		if(grafo.miGrado(C2[rep]) - (2*(tam - 1)) < 0){ resultado = false; }

	} else { if((C2[2] - 4*(tam - 1)) < 0){ resultado = false; } }


/**********************************************************************************/

return resultado;

}



vector<int> CliqueMaximaFronteraLocal::unir(vector<int> CMF, vector<int> aux, bool& tienen_iguales, int& repetido){

int tam = CMF.size();

vector<int> resultado;

	for(int i = 0; i < tam - 1; i++){

		resultado.push_back(CMF[i]);

	}

int frontera = CMF[tam - 1];

if(tienen_iguales){
	if(repetido == 0) {
		resultado.push_back(aux[1]);
		frontera += (grafo.miGrado(aux[1]) - 2*(tam-1));
	} else {
		resultado.push_back(aux[0]);
		frontera += (grafo.miGrado(aux[0]) - 2*(tam-1));
	}
} else {
		resultado.push_back(aux[0]);
		resultado.push_back(aux[1]);
		frontera += (aux[2] - (4*(tam - 1)));
	}

resultado.push_back(frontera);

return resultado;

}



bool tercer_orden(vector<int> v1, vector<int> v2){

	return(v1[2] > v2[2]);

}

ostream& operator<<(ostream &os, list<vector<int> > lista){

list<vector<int> >::iterator it = lista.begin();

int tam = lista.size();

	for(int i = 0; i < tam; i++){

		os << (*it)[0] << " ";
		os << (*it)[1] << " ";
		os << (*it)[2] << " " << endl;
		it++;		

	}

return os;

}

ostream& operator<<(ostream &os, vector<int> &solucion) {
	for(vector<int>::iterator it = solucion.begin(); it != solucion.end(); it++)
		os << (*it) << " ";
	os << endl;
	return os;
}



bool operator==(vector<int> V1, vector<int> V2){

bool resultado = true;
int tam = V1.size();

	for(int i = 0; i < tam; i++){

		if(V1[i] != V2[i]) {resultado = false;}

	}

return resultado;

}
